package main

/**
 * retrun the longest increasing subsequence
 * @param arr int整型一维数组 the array
 * @return int整型一维数组
 */
func LIS(arr []int) []int {
	// write code here
	var result [][]int
	for _, val := range arr {
		var merged = false
		var resultLen = len(result)
		for i := 0; i < resultLen; i++ {
			retArr := result[i]
			var currentLength = len(retArr)
			if val > retArr[currentLength-1] {
				retArr = append(retArr, val)
				result[i] = retArr
			} else if val > retArr[0] {
				for i2, retArrEle := range retArr {
					if retArrEle > val {
						newRetArr := append(retArr[0:i2], val)
						result = append(result, newRetArr)
						break
					}
				}
			}
		}

		if !merged {
			result = append(result, []int{val})
		}
	}

	var longest []int
	var max int = 0
	for _, val := range result {
		if len(val) > max {
			longest = val
			max = len(val)
		}
	}
	return longest
}
